package middle;

import java.util.*;

/**
 * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。
 * 你可以按 任意顺序 返回答案。
 * @author 胡宇轩
 * @Email: programboy@163.com
 */
public class TopKFrequentElements {
    public static void main(String[] args) {
        Solution1 solution = new Solution1();
        solution.topKFrequent(new int[]{1,1,1,2,2,3}, 2);
    }

    /**
     * 利用Java内置的优先队列（大顶堆）解决
     * */
    class Solution {
        public int[] topKFrequent(int[] nums, int k) {
            Map<Integer, Integer> map = new HashMap<>();
            List<Integer> result = new ArrayList<>();
            // 遍历一遍 统计出每个数的出现次数
            for (int i : nums){
                map.put(i, map.getOrDefault(i, 0) + 1);
            }

            // 定义一个优先队列
            PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(map.size(), (o1, o2) -> o2[1] - o1[1]);

            Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
            for (Map.Entry<Integer, Integer> entry : entries){
                priorityQueue.add(new int[]{entry.getKey(), entry.getValue()});
            }
            for (int i = 0; i < k; i++) {
                result.add(Objects.requireNonNull(priorityQueue.poll())[0]);
            }
            return result.stream().mapToInt(Integer::valueOf).toArray();
        }
    }

    /**
     * topK问题 少不了堆，也少不了快排
     * */
    static class Solution1 {
        public int[] topKFrequent(int[] nums, int k) {
            Map<Integer, Integer> map = new HashMap<>();
            List<Integer> res = new ArrayList<>();
            // 遍历一遍 统计出每个数的出现次数
            for (int i : nums){
                map.put(i, map.getOrDefault(i, 0) + 1);
            }
            Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
            int[][] arr = new int[map.size()][];
            int i = 0;
            for (Map.Entry<Integer, Integer> entry : entries){
                arr[i++] = new int[]{entry.getKey(), entry.getValue()};
            }
            int split = quickSort(arr,0, arr.length-1, k);
            for (int j = split; j < arr.length; j++) {
                res.add(arr[j][0]);
            }
            return res.stream().mapToInt(Integer::valueOf).toArray();
        }

        int quickSort(int[][] nums, int l, int r, int k) {
            int size = nums.length;
            int p = l;
            while(l < r) {
                while(l < r && nums[r][1] >= nums[p][1]) {r--;}
                while(l < r && nums[l][1] <= nums[p][1]) {l++;}
                int[] t = nums[r];
                nums[r] = nums[l];
                nums[l] = t;
            }
            int[] t = nums[l];
            nums[l] = nums[p];
            nums[p] = t;

            if(size - l == k){
                return l;
            }
            if(size - l < k){
                return quickSort(nums, p, l-1, k);
            }else{
                return quickSort(nums, l+1, size-1, k);
            }

        }
    }
}
